1. Field of the Invention
The present invention relates to an LRU control apparatus, an LRU control method, and a computer-readable recording medium for selecting an entry to be subjected to LRU control from a plurality of entries included in a storage device.
2. Description of the Related Art
Typically, an LRU (Least Recently Used) control method, which is one of replacement algorithms, is applied to a storage device (such as a main memory and a cache) of an apparatus that performs arithmetic operations according to predetermined programs (such as a general-purpose computer, a supercomputer, and a server) (for example, see Japanese Patent Application Laid-open No. H09-288617). More specifically, the LRU control method is characterized in that histories of how each data is referred in a main memory are retained, and that data that is most unlikely to be referred to hereafter by a CPU (Central Processing Unit) is paged out from the main memory based on the histories. This method intends to avoid a decrease in a processing efficiency caused by an increase in an input/output frequency when data paged out from the main memory is referred to again by the CPU.
For example, conventional LRU control performed when the number of target entries (ways) is four is briefly explained with reference to FIGS. 15 and 16. FIG. 15 depicts what are represented by six bits required for the LRU control over four entries (the entries are denoted as Entries 0, 1, 2, and 3, and A>B represents that A was more recently used). FIG. 16 depicts logic of the LRU control (P_ represents positive, M_ represents negative, “˜” represents NOT, “&” represents AND, and “|” represents OR, and for example a signal of an LRU bit “0” is expressed as P_LRU[0], and a signal of an Entry 0 that cannot be used or selected is expressed as P_DELETE_ENTRY[0]). When a signal of information composed of six bits as shown in FIG. 15 is received and then the signal is applied to the logic as shown in FIG. 16, an entry that was least recently used can be determined.
For example, as shown in FIG. 17(b), Quasi-LRU control that is multi-staged LRU control can reduce the number of bits required when the number of entries is 16, as compared to the LRU control.
In the conventional technique, however, practical control is difficult to perform when the number of entries that are subjected to the LRU control is large, as will be described below. In the quasi-LRU control as the multi-staged LRU control, results of the LRU control may be biased.
That is, it is practical that the conventional LRU control is performed for about four target entries. If the number of target entries is set at 16, the number of required bits becomes 120. Thus, circuit implementation becomes complicated, so that practical control becomes difficult to perform.
Further, in the quasi-LRU control as the multi-staged LRU control, when control is performed with an external entry-unusable/unselectable signal as shown in FIG. 12, there is a concern that results of the LRU control may be biased toward certain entries (or group of lower entries) in some ways of designating unusable or unselectable entries.